/**
 * @param {number} low
 * @param {number} high
 * @param {number} zero
 * @param {number} one
 * @return {number}
 */
// 内存超出限制，怎么优化空间
var countGoodStrings = function(low, high, zero, one) {
    let dp = [], ans = 0, front = -1
    const add = (len) => {
        dp.push(len)
        if(len >= low && len <= high) ans += 1
    }
    add(0)
    front = 0 
    while(dp.length !== 0) {
        let temp = dp
        dp = []
        for(let t of temp) {
            if(t + zero <= high)
                add(t + zero)
            if(t + one <= high)
                add(t + one)
        }
    }
    return ans % (1000000000 + 7)
};
// 爬楼梯 每次只能爬zero或者one步 爬到low-high的任意一个台阶
var countGoodStrings1 = function(low, high, zero, one) {
    const mod = 1e9 + 7
    let ans = 0
    let f = new Array(high + 1).fill(0)  // 构造长度为i的字符串的方法
    f[0] = 1  // 构造空串的方法为1
    for(let i = 1; i <= high; i++) {
        if(i >= one) f[i] = (f[i] + f[i - one]) % mod
        if(i >= zero) f[i] = (f[i] + f[i - zero]) % mod
        if(i >= low) ans = (ans + f[i]) % mod
    }
    return ans
};